package LC;

/**
 * https://leetcode.com/problems/count-primes/description/
 * Description:
 * Count the number of prime numbers less than a non-negative number, n.
 * Credits:
 * Special thanks to @mithmatt for adding this problem and creating all test cases.
 */
public class LC_204_CountPrimes_Array {
    public static void main(String[] args) {
        System.out.println(Solution.countPrimes(10));
    }

    static class Solution {
        static int countPrimes(int n) {
            boolean[] a = new boolean[n];
            for (int i = 2; i * i < n; i++) {
                if (!a[i]) {
                    for (int j = i; i * j < n; j++) {
                        a[i * j] = true;
                    }
                }
            }
            int c = 0;
            for (int i = 2; i < n; i++) {
                if (!a[i]) ++c;
            }
            return c;
        }
    }
}